import java.util.*;

public class BinarryTree {
    static class TreeNode {
        public char ch;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char ch) {
            this.ch = ch;
        }
    }
    //1,2,2,3,4,4,3
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left= H;
        return A;
    }

    public void preOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.ch +" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        preOrder(root.left);
        System.out.print(root.ch +" ");
        preOrder(root.right);
    }

    public static void postOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.ch +" ");
    }
    //求根结点个数
    //法1：
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int tmp = size(root.left) + size(root.right) + 1;
        return  tmp;
    }
    //法2：
    static int size = 0;
    public static void size2(TreeNode root) {
        if(root == null) {
            return;
        }
        size2(root.left);
        size2(root.right);
        size++;
    }
    //求叶结节点个数
    //法1：
    int count = 0;
    public void getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return ;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
       if(root.left == null && root.right == null) {
           count++;
       }
    }

    //法2：
    public int getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
      return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

    //root的第k层有多少个结点
    public int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+
        getKLevelNodeCount(root.right,k-1);
    }

    //获取树的高度
    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
       int leftHeight = getHeight(root.left);
       int rightHeight = getHeight(root.right);
       return Math.max(leftHeight,rightHeight) + 1;
    }

    //检测值为value的元素是否存在
    public TreeNode find(TreeNode root,int val) {
        if(root == null) {
            return null;
        }
        if(root.ch == val) {
            return root;
        }
       TreeNode leftVal = find(root.left, val);
        if(leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right, val);
        if(rightVal != null) {
            return rightVal;
        }
        return null;
    }
    //检查两棵树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null && q != null || q == null && p != null) {
            return false;
        }
        if(p.ch != q.ch) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    //另一棵树的子树
    public boolean isSubTree(TreeNode root, TreeNode subRoot) {
       if(root == null) {
           return false;
       }
       if(isSameTree(root,subRoot)) {
           return true;
        }
       if(isSameTree(root.left,subRoot)) {
           return true;
       }
       if(isSameTree(root.right,subRoot)) {
            return true;
       }
       return false;
    }
    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        if(root.left == null &&  root.right  == null) {
            return root;
        }
        TreeNode tmp;
        tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return false;
        }
       return getHeight1(root) >= 0;
    }

    public int getHeight1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight1(root.left);
        if(leftHeight < 0) {
            return -1;
        }
        int rightHeight = getHeight1(root.right);
        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight)< 2) {
            return Math.max(leftHeight, rightHeight) + 1;
        }else {
            return -1;
        }
    }
    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree == null && rightTree != null || leftTree != null && rightTree == null) {
            return false;
        }
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree.ch != rightTree.ch) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                && isSymmetricChild(rightTree.left,leftTree.right);
    }
    //二叉树的创建和遍历
    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        char ch = str.charAt(i);

        if(ch != '#') {
            root = new TreeNode(ch);
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    private static void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.println(root.ch+" ");
        inorder(root.right);
    }
//    int i = 0;
//    public TreeNode createTree(String str) {
//        TreeNode root = null;
//        char ch = str.charAt(i);
//
//        if(ch != '#') {
//           root = new TreeNode(ch);
//           i++;
//           root.left = createTree(str);
//           root.right = createTree(str);
//        }else {
//            i++;
//        }
//        return root;
//    }
//    private void inorder(TreeNode root) {
//        if(root == null) {
//            return;
//        }
//        inorder(root.left);
//        System.out.println(root.ch+" ");
//        inorder(root.right);

    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> retList = new ArrayList<>();
        if(root == null) {
            return retList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //拿当前队列的节点个数来看的
            int size = queue.size();//2
            List<Character> list = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list.add(cur.ch);
                size--;//0
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            retList.add(list);
        }
        return retList;
    }
    //判断是否为完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }
    //找到该树中两个指定节点的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         if(root == null) {
             return null;
         }
         if(p == root || q == root) {
             return root;
         }
         TreeNode left = lowestCommonAncestor(root.left,p,q);
         TreeNode right = lowestCommonAncestor(root.right,p,q);
         if(left != null && right != null) {
             return root;
         } else if(left != null) {
             return left;
         }else {
             return right;
         }
    }

    public boolean getPath(TreeNode root,TreeNode node) {
        if(root == null) {
            return false;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flgLeft = getPath(root.left,node);
        if(flgLeft) {
            return true;
        }
        boolean flgRight = getPath(root.right,node);
        if(flgRight) {
            return true;
        }
        stack.pop();
        return false;
    }
    //找到该树中两个指定节点的最近公共祖先
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
       Stack<TreeNode> stack1 = new Stack<>();
       Stack<TreeNode> stack2 = new Stack<>();
       getPath(root,p);
       getPath(root,q);
       int sizeP = stack1.size();
       int sizeQ = stack2.size();

       if(sizeP - sizeQ > 0) {
           int size = sizeP - sizeQ;
           while(size != 0) {
               stack1.pop();
               size--;
           }
       }
       if(sizeQ - sizeP > 0) {
           int size = sizeQ - sizeP;
           while(size != 0) {
               stack2.pop();
               size--;
           }
       }
       while(!stack1.isEmpty() && !stack2.isEmpty()) {
           if (!stack1.peek().equals(stack2.peek()) ) {
               stack1.pop();
               stack2.pop();
           }else {
               return stack1.peek();
           }
       }
      return null;
    }
}
 